package com.yun.algorithmproblem.leetcode;

public class Leetcode808 {
    public static void main(String[] args) {
        Leetcode808 obj = new Leetcode808();
        int n = 50;
        System.out.println(obj.soupServings(n));
    }

    public double soupServings(int n) {
        if (n >= 4451) {
            return 1;
        }

        n = (n + 24) / 25;
        double[][] memo = new double[n + 1][n + 1];
        return dfs(n, n, memo);
    }

    private double dfs(int a, int b, double[][] memo) {
        if (a <= 0 && b <= 0) {
            return 0.5;
        }
        if (a <= 0) {
            return 1;
        }
        if (b <= 0) {
            return 0;
        }
        if (memo[a][b] == 0) {
            memo[a][b] = (dfs(a - 4, b, memo) + dfs(a - 3, b - 1, memo) + dfs(a - 2, b - 2, memo) + dfs(a - 1, b - 3, memo)) / 4;
        }
        return memo[a][b];
    }
}
